Due to the recent explosion of Internet use, there has been an enormous increase in data or traffic flow being sent over communication networks. This has led to a huge increase in bandwidth requirements by operators which is expensive. A problem with handling traffic flow is that it is difficult to estimate due to the “bursty” nature of traffic flows. For example, if someone decides to send video data to another source over a communications network, it uses a lot of bandwidth. A solution to this problem is that when network operators are allocating bandwidth to a node or a router, a large amount of bandwidth is allocated to that node to handle any of the bursty traffic. This is very wasteful of bandwidth.
Various methods and systems have been employed to control the admission of traffic flows in packet switch networks such as Internet Protocol (IP) based networks which includes traditional IP, IntServ, DiffServ and MPLS networks as well as ATM and Frame Relay. It is important to have a reliable estimation of resources required to meet quality of service performance requirements. The estimation of resources can be based on the usage of measurement and estimation of effective bandwidth. At present it is impractical to estimate the required resource for each traffic flow separately on-line for a number of reasons, including scalability, as well as the fact that many traffic flows exist only for a short period of time, especially in IP based networks. It is more practical to estimate effective bandwidth for traffic aggregates comprising many flows.
The effective bandwidth of a variable bit rate traffic flow is a measure that summarises statistical properties of the traffic flow into just one value, while taking into account the quality of service requirements such as cell loss ratio, delay, and other parameters. Also, the bandwidth estimation of the effective bandwidth can take into account some other parameters such as link, bandwidth, buffer size, etc.
Loss and delay of data packets at a node in the network arise from the queuing of packets in the buffers of switches or routers. Buffers are required to cope with fluctuations in the bit-rate on incoming links. However, if the buffers are too small, packets will be lost as a result of buffer overflow; if the buffers are too large, some packets will experience unacceptable delays. For a given buffer-size, loss and delay can be reduced by increasing the capacity of the outgoing link.
To eliminate packet loss entirely, it would be necessary to increase the capacity of the outgoing link to equal the sum of the capacities of the incoming links. This is prohibitively expensive. Nevertheless, it is a strategy employed sometimes by network operators who take a conservative view on assuring network quality of service.
There is a better way. It is unnecessary to eliminate packet loss and unacceptable packet delay in order to give satisfactory perceived quality. It is enough to keep their frequency within predetermined bounds. These bounds are referred to as Quality of Service (QoS) targets.
The optimal way to ensure satisfactory perceived quality is to provide the minimum capacity that will guarantee the QoS targets. This minimum capacity is referred to as the Bandwidth Requirement (BWR) of the bit-stream. It lies somewhere between mean rate and the peak-rate requirement.
The existence of a BWR and its value can be demonstrated experimentally with a router by observing the change in the frequency with which a target queuing delay in an output buffer is exceeded when the capacity of the outgoing link is varied.
The mean-rate and the peak-rate doe not depend on the QoS targets. For bursty traffic, the peak-rate can be many multiples of the mean-rate. As the QoS target changes, the BWR varies between them.
For a given QoS target, the BWR depends strongly on the nature of the traffic. There is no universal multiplier than can be applied to the mean-rate or peak-rate to give the BWR for a given QoS target.
This opens the way for many applications: monitoring network quality levels, QoS-sensitive service provisioning, IP call admission control, traffic-based billing and capacity planning.
Prior Art disclosed, for example in Duffield, Lewis et al. [IEEE Journal for Selected Areas in Communications, August 1995] shows that the relevant statistical data required for the determination of BWR can be encapsulated in a single function, namely, the Scaled Cumulant Generating Function [sCGF]. An invention disclosed in U.S. Pat. No. 6,580,691 (Bjoerkman et al), discloses a method and system for estimating the sCGF on-line in real time and storing it as a compact traffic descriptor. This publication relates to inelastic traffic which estimates the bandwidth requirement for a traffic flow on-line.
Essentially, therefore, given the buffer size b and the QoS target Q, the BWR of a node in the communications system can be calculated from the traffic descriptor D. It will be appreciated that the traffic descriptor, which is essentially the statistical properties of the data, is all important. That descriptor must contain sufficient relative and statistical information to allow computation of the bandwidth requirement. Essentially, the traffic descriptor D describes the characteristics of the particular traffic.
On-line implementation of the estimation of the effective bandwidth is complicated due to a number of reasons, such as performance related constraints, measurements and estimation, technique constraints, router constraints and measurement point constraints. The affect of all these factors is that on-line estimation of effective bandwidth at a node has not been achieved accurately.
The estimation of the effective bandwidth of a traffic flow consumes router resources. Therefore, it is impractical to estimate the effective bandwidth for each traffic flow when the number of flows becomes too large. Such a straight forward approach leads to a scalability problem as the number of flows increase. Some models used in the estimation of the effective bandwidth rely on parameters that are either difficult to measure effectively or reliably. An example of such a parameter is the peak rate of flow. The peak rate of flow is very sensitive to local fluctuations of traffic flow. It's estimation is often based on averaging over a small period of time and it is either over estimated or under estimated. It has been found that the declaration of peak rate is not accurate thus it does not provide a full remedy to the problem.
Router constraints is a problem because the buffer counters within the router provide raw information for estimation of effective bandwidth only. Some routers provide access to counters at output buffers but for bandwidth estimation purposes, it is not an accurate estimation. This is also applicable to other types of network elements including switches or bridges.
The mean rate of traffic flow is a good characteristic for bandwidth estimation. Mean rate is a very robust characteristic of traffic flow. In particular, it is not practically sensitive to local short term fluctuations in flow rate. Mean rate is relatively simple to measure. For this reason, it is very desirable to use the mean rate as the basis for estimation of effective bandwidth. Unfortunately, in general the mean rate of the source does not reflect a network resource required for a flow to meet quality of service requirements. It has also been found that the direct usage of mean rate, together, for example, with the peak rate for the estimation of the effective bandwidth can lead to inaccurate results. A principal drawback of such a method or system, as already mentioned, is that the peak rate is very sensitive to local fluctuations of traffic and is difficult to measure.
In the paper F. P. Kelly “Effective Bandwidths at Multi-class Queues”, Queuing Systems 9, 1991, pp 5-16” a method for the estimation of the effective bandwidth of an individual flow is proposed. In principle this method can be used for the off-line estimation of the effective bandwidth required. For on-line usage however it is too time consuming. The other disadvantage of this method is that it does not take into account buffer size and as a consequence of this it does not deal with any delays. The paper does not propose a method for estimating effective bandwidth on-line accurately.
In another paper D. D. Botvich & N. G. Duffield “Large Deviations, Economies of Scale, and the Shape of the Loss Curve in Large Multiplexers” Queuing Systems 20, 293-320 (1995) investigates the behaviour of the effective bandwidth in the situation when the number of traffic sources is increased. The economy of scale in this case is evaluated and estimated for properly chosen scaling. This paper provides a theoretical basis for estimating the effective bandwidth for a number of flows off-line.
PCT Patent Application No. PCT/IE98/00013 “Telia Research AB et al” discloses a general method for the estimation of the effective bandwidth applicable both to individual flows and traffic aggregates. This method is flexible and accurate for the estimation of effective bandwidth for individual flows. This method can be used both off-line and on-line. The on-line implementation however has some limitations due to the fact that most of today's routers and switches are not able to provide sufficiently accurate “raw” measurement data. Thus, the on-line estimation of effective bandwidth is invariably inaccurate for a large number of flows.
In this specification, the term “traffic flow” is used interchangeably with other terms including “call” and “connection”. It will be appreciated to someone skilled in the art that the term “traffic flow” is used in IP based networks, while the terms “call” and “connection” are used in ATM networks. For this reason we also use terms “packet” and “cell” interchangeably. Further, in this specification, we use the terms “measurement” and “estimation” in a different way. We refer to measurement as the process of collecting the raw traffic information. The estimation process uses the data collected from the measurement process.
The terminology of this specification is generally that which is used in High-Performance Communication Networks [Jean Walrand and Pravin Varaiya (Second Edition) Academic Press 2000], unless clearly otherwise.